2018.4.24 还是DP....

今天3题，就最后一题涉及贪心，DP的看了一下disscuss

Array - 219. Contains Duplicate II

题目详情

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

查找有没相同的值，但是索引(i j不同)不同，且他们的索引距离小于k，有返回true

Example:

Input: matrix = [0, 1, 0, 1, 12], k = 3

Output: true

思路

• 跟数组去重一样，利用键值对，值存储索引值，键值存储值

具体代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function(nums, k) {
    let obj = {}
    for(let i = 0, len = nums.length; i < len; i++) {
        if(obj[nums[i]] !== undefined) {
            if(Math.abs(obj[nums[i]] - i) <= k) {
                return true
            }
            obj[nums[i]] = i
        } else {
            obj[nums[i]] = i
        }
    }
    return false
};

---

Array - 643. Maximum Average Subarray I

题目详情

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

在数组中找到长度为k的最大值除以k的值。其实就是找到长度为>k的最大值

Example:

Input: [1,12,-5,-6,50,3], k = 4

Output: 12.75

思路

• 先求前 k - 1长度数组的和
• 然后遍历数组，从k-1开始加，之后就加一个尾减个头，这样保证长度不变。

具体代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findMaxAverage = function(nums, k) {
    if(nums.length === 1) return nums[0]
    
    let currSum = 0
    for(let i = 0; i < k - 1; i++) {
        currSum += nums[i]
    }
    if(nums.length === k) return (currSum + nums[k - 1]) / k
    
    let maxSum = -Infinity
    for(let i = k - 1, len = nums.length; i < len; i++) {
        currSum += nums[i]
        if(i - k > -1) {
            currSum -= nums[i - k]
        }
        maxSum = Math.max(currSum, maxSum)
    }
    return maxSum / 1.0 / k
};

---

Array - 605. Can Place Flowers

题目详情

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

这道题给了我们一个01数组，其中1表示已经放了花，0表示可以放花的位置，但是有个限制条件是不能有相邻的花。

Example:

Input: flowerbed = [1,0,0,0,1], n = 1

Output: True

思路

• 遍历数组，在为0的元素，判断该元素前后是否为0
• 如果是，判断该位置前后是不是有花
• 没有花就在该位置种花，种花次数和n相等

具体代码

/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function(arr, n) {
    let count = 0
    for(let i = 0, len = arr.length; i < len && count < n; i++) {
        if(arr[i] === 0) {
            let prev = i === 0 ? 0 : arr[i - 1]
            let next = i === len - 1 ? 0 : arr[i + 1]
            if(prev === 0 && next === 0) {
                arr[i] = 1
                count ++
            }
        }
    }
    console.log(count)
    return count === n
};